import functools


class Solution:
    def mergeStones(self, stones, k: int) -> int:
        n = len(stones)
        if n < k and n != 1:
            return -1
        for i in range(1, n):
            stones[i] += stones[i - 1]

        @functools.cache
        def dfs(i, j, t):
            if j - i + 1 <= t:
                return 0
            if (j - i + 1 - t) % (k - 1):
                return float('inf')
            else:
                if t == 1:
                    min_val = float('inf')
                    if i == 0:
                        now_val = stones[j]
                    else:
                        now_val = stones[j] - stones[i - 1]
                    for v in range(i, j):
                        for next_t in range(1, k):
                            min_val = min(now_val + dfs(i, v, next_t) + dfs(v + 1, j, k - next_t), min_val)
                else:
                    min_val = float('inf')
                    for v in range(i, j):
                        for next_t in range(1, t):
                            min_val = min(min_val, dfs(i, v, next_t) + dfs(v + 1, j, t - next_t))
                return min_val
        val = dfs(0, n - 1, 1)
        if val < float('inf'):
            return val
        else:
            return -1

class Solution:
    def mergeStones(self, stones, k: int) -> int:
        n = len(stones)
        if n < k and n != 1:
            return -1
        for i in range(1, n):
            stones[i] += stones[i - 1]

        @functools.cache
        def dfs(i, j, t):
            if j - i + 1 <= t:
                return 0
            if (j - i + 1 - t) % (k - 1):
                return float('inf')
            else:
                if t == 1:
                    min_val = float('inf')
                    if i == 0:
                        now_val = stones[j]
                    else:
                        now_val = stones[j] - stones[i - 1]
                    for v in range(i, j):
                        min_val = min(now_val + dfs(i, v, 1) + dfs(v + 1, j, k - 1), min_val)
                else:
                    min_val = float('inf')
                    for v in range(i, j):
                        for next_t in range(1, t):
                            min_val = min(min_val, dfs(i, v, next_t) + dfs(v + 1, j, t - next_t))
                return min_val
        val = dfs(0, n - 1, 1)
        if val < float('inf'):
            return val
        else:
            return -1
data = Solution()
# stones = [3, 5, 1, 2, 6]
# k = 3
# print(data.mergeStones(stones, k))
stones = [7,7,8,6,5,6,6]
k = 3
print(data.mergeStones(stones, k))